Luogu P3693 琪露诺的冰雪小屋 题解

Posted on | In |
Words count in article: 6.1k | Reading time ≈ 34

超级大模拟，简直写的我头疼，但终于还是A掉了，所以来写一篇题解QwQ

首先，我们不管别的，拿20分再说，然后我们发现20分其实挺好拿的啊，瞎jb搞一搞分就来了。以下是20分核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int num;//这是⑨现在有的冰砖数量
int frz[MAXN][MAXN];//frz数组记录地面的冷冻值,如果有冰砖则为inf
il int Spell_Card(int x,int y,int dir,int s)//弹幕操作，暴力搞就完了
{
    int ret=0;
    for(ri i=0;i<=s;i++)
    {
        int Xi,Yi;
        switch(dir)
        {
            case 0:Xi=x-i,Yi=y;break;
            case 1:Xi=x-i,Yi=y-i;break;
            case 2:Xi=x,Yi=y-i;break;
            case 3:Xi=x+i,Yi=y-i;break;
            case 4:Xi=x+i,Yi=y;break;
            case 5:Xi=x+i,Yi=y+i;break;
            case 6:Xi=x,Yi=y+i;break;
            case 7:Xi=x-i,Yi=y+i;break;
        }
        if(Xi<0||Xi>=n||Yi<0||Yi>=n||frz[Xi][Yi]==inf)
            break;
        else if(frz[Xi][Yi]==4)
            continue;
        else
        {
            frz[Xi][Yi]++;
            ret++;
        }
    }
    return ret;
}
il int Make()//做冰砖，直接n*n枚举每一块地面就行了
{
    int ret=0;
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
            if(frz[i][j]==4)
                frz[i][j]=0,ret++,num++;
    return ret;
}

20分之后，我们会发现30分其实也挺好写的，于是瞎搞一下就又多了10分。以下是30分核心（其实就是PUT_ICE_BLOCK的操作了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
il void Put(int r,int c,int h)
{
    if(num==0)
    {
        printf("CIRNO HAS NO ICE_BLOCK\n");
        return;
    }
    else if(vis[r][c][h]||(h>0&&!vis[r-1][c][h]&&!vis[r+1][c][h]&&!vis[r][c-1][h]&&!vis[r][c+1][h]&&!vis[r][c][h-1]&&!vis[r][c][h+1]))
    {
        printf("BAKA CIRNO,CAN'T PUT HERE\n");
        return;
    }
    else if(r<Hr||r>Hr+Hx-1||c<Hc||c>Hc+Hy-1)
    {
        printf("CIRNO MISSED THE PLACE\n");
        vis[r][c][h]=1;
        num--;
        if(h==0)
            frz[r][c]=inf;
        return;
    }
    else if(r>=Hr+1&&r<=Hr+Hx-2&&c>=Hc+1&&c<=Hc+Hy-2)
    {
        printf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE\n");
        vis[r][c][h]=1;
        num--;
        if(h==0)
            frz[r][c]=inf;
        return;
    }
    else
    {
        vis[r][c][h]=1;
        num--;
        printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S)\n",num);
        if(h==0)
            frz[r][c]=inf;
        return;
    }
}

别看我打得长，其实没多大的思维难度，毕竟出题人很仁慈地把位置位于屋内屋外的判定条件都给出来了，直接抄就行了。

要注意的有两点：

  1. “可依靠的方块”为上下左右前后六个方向，对没错，上面也可以。
  2. 一定要判定h=0，即冰砖放在地上的情况，要将frz[r][c]修改为inf。
    然后就没太大问题了。

30分之后，我们遇到了第一个难题：如何判断悬空联通块。

实际上，如果BFS学的比较熟练的几乎不需要思考，在移除方块之后向6个方向做BFS就完了，如果搜到了h=0的方块，就可以保留，如果搜完了还没有遇到h=0的方块，那么这就是一个悬空联通块了，这个时候所有进过队的方块都要删掉，删掉并统计一下就行了。

以下是50分的核心：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int f[MAXN][MAXN][MAXN];//每个方块所属的联通块
int dx[]={0,0,0,0,1,-1};
int dy[]={0,0,1,-1,0,0};
int dz[]={1,-1,0,0,0,0};
bool vis[MAXN][MAXN][MAXN];
struct node
{
    int x,y,z;
};
node q[MAXN];
il bool BFS(int r,int c,int h,int dir)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri i=0;i<6;i++)
        {
            node v=(node){u.x+dx[i],u.y+dy[i],u.z+dz[i]};
            if(vis[v.x][v.y][v.z]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
        for(ri i=1;i<=fr;i++)
            vis[q[i].x][q[i].y][q[i].z]=0;//对悬空联通块的处理
    return flag;
}
il void Remove(int r,int c,int h)
{
    if(!vis[r][c][h])
    {
        printf("BAKA CIRNO,THERE IS NO ICE_BLOCK\n");
        return;
    }
    else
    {
        num++,
        vis[r][c][h]=0;
        if(h==0)
            frz[r][c]=0;
        memset(f,-1,sizeof(f));
        int brk=0;
        for(ri i=0;i<6;i++)
        {
            int R=r+dx[i],C=c+dy[i],H=h+dz[i];
            if(f[R][C][H]!=-1||!vis[R][C][H])//对6个方向做BFS
                continue;
            else if(!BFS(R,C,H,i))
                brk+=fr;
            else
                continue;
        }
        printf("CIRNO REMOVED AN ICE_BLOCK");
        if(brk>0)
            printf(",AND %d BLOCK(S) ARE BROKEN",brk);
        printf("\n");
    }
}

写到这里也许你们会说：这也不是特别难啊，题面又长，还特别水，结果4/5不是一下就打完了吗？然而出题人表示这才刚刚开始呢。

先来看70分，建造屋顶时没有塌陷与方块掉落，也就是说不用BFS，可是我们注意到之前的BFS改造一下就可以放过来用，于是就可以直接冲90分了。

以下是90分部分核心：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
il bool BFS(int r,int c,int h,int dir,bool last)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri i=0;i<6;i++)
        {
            node v=(node){u.x+dx[i],u.y+dy[i],u.z+dz[i]};
            if(vis[v.x][v.y][v.z]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
    {
        if(!last)
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0;
        else
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0,num++;
    }
    return flag;
}

修改之后的BFS，增加一个last标记，判定是否为MAKE_ROOF时进行的。是，则由于题目条件给出，对悬空联通块中的冰砖进行回收。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
bool perfect=1;
il int Get_Height()
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            int h=0;
            for(ri k=Hm;k;k--)
                if(vis[i][j][k])
                {
                    h=k;
                    break;
                }
            ret=max(ret,h);
        }
    return ret+1;
}//房屋高度
il int Get_Need(int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
            if(!vis[i][j][h])
                vis[i][j][h]=1,ret++;
    return ret;
}
il bool Check_place(int x,int y)
{
    if(x==Hr||x==Hr+Hx-1)
    {
        if(Hy%2)
        {
            if(y==(Hc+(Hc+Hy-1))/2)
                return 1;
        }
        else
            if(y==(Hc+(Hc+Hy-1))/2||y==(Hc+(Hc+Hy-1))/2+1)
                return 1;
    }
    else if(y==Hc||y==Hc+Hy-1)
    {
        if(Hx%2)
        {
            if(x==(Hr+(Hr+Hx-1))/2)
                return 1;
        }
        else
            if(x==(Hr+(Hr+Hx-1))/2||x==(Hr+(Hr+Hx-1))/2+1)
                return 1;
    }
    return 0;
}//判断一个坐标是否在某面墙的正中间
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            if(!vis[i][j][0]&&!vis[i][j][1])
            {
                if((x==-1&&y==-1)||(!Check_place(x,y)&&Check_place(i,j)))
                    x=i,y=j,flag=1;
            }
        }
    return flag;
}//判断是否有完整的门
il void Get_door_place(int &x,int &y)
{
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            if(!vis[i][j][0]||!vis[i][j][1])
            {
                if((x==-1&&y==-1)||(!Check_place(x,y)&&Check_place(i,j)))
                    x=i,y=j;
            }
        }
}//寻找门的位置
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            for(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    return ret;
}//墙上的空缺也是暴力枚举
il int Check_Corner(int h)
{
    int ret=0;
    for(ri i=0;i<h;i++)
    {
        if(!vis[Hr][Hc][i])
            ret++;
        if(!vis[Hr][Hc+Hy-1][i])
            ret++;
        if(!vis[Hr+Hx-1][Hc][i])
            ret++;
        if(!vis[Hr+Hx-1][Hc+Hy-1][i])
            ret++;
    }
    return ret;
}//枚举四个角落寻找空缺
il void Fix(int h)
{
    bool door=0,corner=0;
    int x=-1,y=-1;
    door=Check_Door(x,y);//检查是否有完整的门
    if(!door)
        Get_door_place(x,y);//没有完整的门就寻找只需要拆掉一块冰砖的位置
    int need=Get_need(x,y,h);//墙上的空缺
    if(num<need)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL\n");
        return;
    }
    num-=need;
    printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE\n");
    if(!door)
        printf("HOUSE HAS NO DOOR\n"),perfect=0;
    else
        printf("DOOR IS OK\n");
    if(need>0)
        printf("WALL NEED TO BE FIXED\n"),perfect=0;
    else
        printf("WALL IS OK\n");
    need=Check_Corner(h);//角落的空缺
    if(need>0)
        printf("CORNER NEED TO BE FIXED\n"),perfect=0;
    else
        printf("CORNER IS OK\n");
    if(need>num)
        num=0;
    else
        num-=need;
    printf("CIRNO FINALLY HAS %d ICE_BLOCK(S)\n",num);
    if(perfect)
        printf("CIRNO IS PERFECT!\n");
}
il void Remove_Blocks(int h)
{
    memset(f,-1,sizeof(f));
    if(!BFS(Hr,Hc,h,0,1))
    {
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n");
        return;
    }//优先判断屋顶塌陷的情况
    int dir=1;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            for(ri k=0;k<h;k++)
                if(vis[i][j][k]&&f[i][j][k]==-1)
                    BFS(i,j,k,dir++,1);
        }//回收墙上的悬空联通块
    Fix(h);//修复
}
il void Make_Roof()
{
    int h=Get_Height();//获取屋顶高度
    int need=Get_Need(h);//获取建造屋顶所需数量
    if(num<need)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF\n");
        return;
    }\\砖块不够
    int S=(Hx-2)*(Hy-2)*h;//计算内部空间
    if(h<2||S<2)
    {
        printf("SORRY CIRNO,HOUSE IS TOO SMALL\n");
        return;
    }//空间不足
    num-=need;
    int num1=0,num2=0;//num1-->屋内|num2-->屋外
    for(ri i=Hr+1;i<=Hr+Hx-2;i++)
        for(ri j=Hc+1;j<=Hc+Hy-2;j++)
        {
            for(ri k=0;k<h;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num1++,num++,perfect=0;
            for(ri k=h+1;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;//注意,这里是一个大坑。
        }//回收屋内冰砖
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
        {
            if(i>=Hr&&i<=Hr+Hx-1&&j>=Hc&&j<=Hc+Hy-1)
                continue;
            for(ri k=0;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;
        }//回收屋外冰砖
    printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED\n",num1);
    printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED\n",num2);
    Remove_Blocks(h);
}

这样大概就有90-95分了，要注意的是封上屋顶后，高于h的冰砖也算是屋外冰砖了。

然后我们会发现第二组数据非常的奇怪，墙壁上没有空缺标准输出却有WALL NEED TO BE FIXED，而本有空缺的角落却输出了CORNER IS OK。怎么回事呢？数据有问题吗？不是，如果再回去仔细读题会发现题目对墙壁有残缺的定义是“在屋内能看到缺口”，而#2的情况中，门被开在了角落旁边，这样角落的空缺就能被看见了。

那么怎么办？只判定门的位置是否在中间的方法肯定不行了，单独打特判的话绝对会疯掉，毕竟我不想再像出题人那样为10分多打200行。于是我想到了对每个可能作为门的位置进行估价，选取估价较高的位置作为门。

以下是核心部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
il bool Mid(int x,int y)
{
    if(x==Hr||x==Hr+Hx-1)
    {
        if(Hy%2)
        {
            if(y==(Hc+(Hc+Hy-1))/2)
                return 1;
        }
        else
            if(y==(Hc+(Hc+Hy-1))/2||y==(Hc+(Hc+Hy-1))/2+1)
                return 1;
    }
    else if(y==Hc||y==Hc+Hy-1)
    {
        if(Hx%2)
        {
            if(x==(Hr+(Hr+Hx-1))/2)
                return 1;
        }
        else
            if(x==(Hr+(Hr+Hx-1))/2||x==(Hr+(Hr+Hx-1))/2+1)
                return 1;
    }
    return 0;
}//这就是之前的Check_door_placeQwQ
il int Corner(int x,int y,bool last)
{
    int ret=0;
    if((x==Hr&&y==Hc+1)||(x==Hr+1&&y==Hc))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr][Hc][i])
            {
                ret++;
                if(last)
                    vis[Hr][Hc][i]=1;
            }
    }
    if((x==Hr+Hx-1&&y==Hc+1)||(x==Hr+Hc-2&&y==Hc))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr+Hx-1][Hc][i])
            {
                ret++;
                if(last)
                    vis[Hr+Hx-1][Hc][i]=1;
            }
    }
    if((x==Hr&&y==Hc+Hy-2)||(x==Hr+1&&y==Hc+Hy-1))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr][Hc+Hy-1][i])
            {
                ret++;
                if(last)
                    vis[Hr][Hc+Hy-1][i]=1;
            }
    }
    if((x==Hr+Hx-1&&y==Hc+Hy-2)||(x==Hr+Hc-2&&y==Hc+Hy-1))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr+Hx-1][Hc+Hy-1][i])
            {
                ret++;
                if(last)
                    vis[Hr+Hx-1][Hc+Hy-1][i]=1;
            }
    }
    return ret;
}//也是暴力，懒的解释了QwQ
il int Evaluate(int x,int y)
{
    int ret=0;
    for(ri i=0;i<2;i++)
        if(!vis[x][y][i])
            ret+=1000;//由于我们优先选择更完整的空隙作为门，所以完整度的估价最高
    if(Mid(x,y))
        ret+=100;//中间的位置仅次于完整度
    int A=Corner(x,y,0);//获取当前位置是否在角落旁边和与其相邻的角落有多少空缺
    ret+=((5-A)*10)//空缺越少估价越高;
    return ret;
}
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            if(!vis[i][j][0]||!vis[i][j][1])
            {
                if((x==-1&&y==-1)||Evaluate(i,j)>Evaluate(x,y))
                    x=i,y=j,flag=1;
            }
        }
    int E=Evaluate(x,y);
    if(flag)
    {
    	if((E/1000)%10==2)
    		return 1;
    	return 0;
    }//找千位数就可以知道是否完整了
    return flag;
}
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            for(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    int E=Evaluate(x,y);
    ret+=(5-(E/10)%10);
    Corner(x,y,1);//如果角落有空缺也要补上
    return ret;
}

然后就可以AC了，实际上最后10分也不需要200+排对吧QwQ

以下是完整代码（504排，比出题人写的题解大概少了60排吧，并不压行QwQ）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;
const int N=2000000+110;
const int inf=0x7fffffff;
const int MAXN=50;
const double eps=1e-8;
il int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
il void Getstr(char ch[])
{
    char c=getchar();
    int len=-1;
    while(c<'A'||c>'Z')
        c=getchar();
    while((c>='A'&&c<='Z')||c=='_')
    {
        ch[++len]=c;
        c=getchar();
    }
}
int n,m,num,fr,tl;
int Hm,Hr,Hc,Hx,Hy;
int frz[MAXN][MAXN],f[MAXN][MAXN][MAXN];
int dx[]={0,0,0,0,1,-1};
int dy[]={0,0,1,-1,0,0};
int dz[]={1,-1,0,0,0,0};
bool perfect=1;
bool vis[MAXN][MAXN][MAXN];
struct node
{
    int x,y,z;
};
node q[MAXN];
il int Spell_Card(int x,int y,int dir,int s)
{
    int ret=0;
    for(ri i=0;i<=s;i++)
    {
        int Xi,Yi;
        switch(dir)
        {
            case 0:Xi=x-i,Yi=y;break;
            case 1:Xi=x-i,Yi=y-i;break;
            case 2:Xi=x,Yi=y-i;break;
            case 3:Xi=x+i,Yi=y-i;break;
            case 4:Xi=x+i,Yi=y;break;
            case 5:Xi=x+i,Yi=y+i;break;
            case 6:Xi=x,Yi=y+i;break;
            case 7:Xi=x-i,Yi=y+i;break;
        }
        if(Xi<0||Xi>=n||Yi<0||Yi>=n||frz[Xi][Yi]==inf)
            break;
        else if(frz[Xi][Yi]==4)
            continue;
        else
        {
            frz[Xi][Yi]++;
            ret++;
        }
    }
    return ret;
}
il int Make()
{
    int ret=0;
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
            if(frz[i][j]==4)
                frz[i][j]=0,ret++,num++;
    return ret;
}
il void Put(int r,int c,int h)
{
    if(num==0)
    {
        printf("CIRNO HAS NO ICE_BLOCK\n");
        return;
    }
    else if(vis[r][c][h]||(h>0&&!vis[r-1][c][h]&&!vis[r+1][c][h]&&!vis[r][c-1][h]&&!vis[r][c+1][h]&&!vis[r][c][h-1]&&!vis[r][c][h+1]))
    {
        printf("BAKA CIRNO,CAN'T PUT HERE\n");
        return;
    }
    else if(r<Hr||r>Hr+Hx-1||c<Hc||c>Hc+Hy-1)
    {
        printf("CIRNO MISSED THE PLACE\n");
        vis[r][c][h]=1;
        num--;
        if(h==0)
            frz[r][c]=inf;
        return;
    }
    else if(r>=Hr+1&&r<=Hr+Hx-2&&c>=Hc+1&&c<=Hc+Hy-2)
    {
        printf("CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE\n");
        vis[r][c][h]=1;
        num--;
        if(h==0)
            frz[r][c]=inf;
        return;
    }
    else
    {
        vis[r][c][h]=1;
        num--;
        printf("CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS %d ICE_BLOCK(S)\n",num);
        if(h==0)
            frz[r][c]=inf;
        return;
    }
}
il bool BFS(int r,int c,int h,int dir,bool last)
{
    fr=1,tl=0;
    q[1]=(node){r,c,h};
    f[r][c][h]=dir;
    bool flag=0;
    while(tl<fr)
    {
        node u=q[++tl];
        if(u.z==0)
            flag=1;
        for(ri i=0;i<6;i++)
        {
            node v=(node){u.x+dx[i],u.y+dy[i],u.z+dz[i]};
            if(vis[v.x][v.y][v.z]&&f[v.x][v.y][v.z]==-1)
            {
                q[++fr]=v;
                f[v.x][v.y][v.z]=dir;
            }
        }
    }
    if(!flag)
    {
        if(!last)
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0;
        else
            for(ri i=1;i<=fr;i++)
                vis[q[i].x][q[i].y][q[i].z]=0,num++;
    }
    return flag;
}
il void Remove(int r,int c,int h)
{
    if(!vis[r][c][h])
    {
        printf("BAKA CIRNO,THERE IS NO ICE_BLOCK\n");
        return;
    }
    else
    {
        num++,
        vis[r][c][h]=0;
        if(h==0)
            frz[r][c]=0;
        memset(f,-1,sizeof(f));
        int brk=0;
        for(ri i=0;i<6;i++)
        {
            int R=r+dx[i],C=c+dy[i],H=h+dz[i];
            if(f[R][C][H]!=-1||!vis[R][C][H])
                continue;
            else if(!BFS(R,C,H,i,0))
                brk+=fr;
            else
                continue;
        }
        printf("CIRNO REMOVED AN ICE_BLOCK");
        if(brk>0)
            printf(",AND %d BLOCK(S) ARE BROKEN",brk);
        printf("\n");
    }
}
il int Get_Height()
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            int h=0;
            for(ri k=Hm;k;k--)
                if(vis[i][j][k])
                {
                    h=k;
                    break;
                }
            ret=max(ret,h);
        }
    return ret+1;
}
il int Get_Need(int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
            if(!vis[i][j][h])
                vis[i][j][h]=1,ret++;
    return ret;
}
il bool Mid(int x,int y)
{
    if(x==Hr||x==Hr+Hx-1)
    {
        if(Hy%2)
        {
            if(y==(Hc+(Hc+Hy-1))/2)
                return 1;
        }
        else
            if(y==(Hc+(Hc+Hy-1))/2||y==(Hc+(Hc+Hy-1))/2+1)
                return 1;
    }
    else if(y==Hc||y==Hc+Hy-1)
    {
        if(Hx%2)
        {
            if(x==(Hr+(Hr+Hx-1))/2)
                return 1;
        }
        else
            if(x==(Hr+(Hr+Hx-1))/2||x==(Hr+(Hr+Hx-1))/2+1)
                return 1;
    }
    return 0;
}
il int Corner(int x,int y,bool last)
{
    int ret=0;
    if((x==Hr&&y==Hc+1)||(x==Hr+1&&y==Hc))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr][Hc][i])
            {
                ret++;
                if(last)
                    vis[Hr][Hc][i]=1;
            }
    }
    if((x==Hr+Hx-1&&y==Hc+1)||(x==Hr+Hc-2&&y==Hc))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr+Hx-1][Hc][i])
            {
                ret++;
                if(last)
                    vis[Hr+Hx-1][Hc][i]=1;
            }
    }
    if((x==Hr&&y==Hc+Hy-2)||(x==Hr+1&&y==Hc+Hy-1))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr][Hc+Hy-1][i])
            {
                ret++;
                if(last)
                    vis[Hr][Hc+Hy-1][i]=1;
            }
    }
    if((x==Hr+Hx-1&&y==Hc+Hy-2)||(x==Hr+Hc-2&&y==Hc+Hy-1))
    {
        for(ri i=0;i<2;i++)
            if(!vis[Hr+Hx-1][Hc+Hy-1][i])
            {
                ret++;
                if(last)
                    vis[Hr+Hx-1][Hc+Hy-1][i]=1;
            }
    }
    return ret;
}
il int Evaluate(int x,int y)
{
    int ret=0;
    for(ri i=0;i<2;i++)
        if(!vis[x][y][i])
            ret+=1000;
    if(Mid(x,y))
        ret+=100;
    int A=Corner(x,y,0);
    ret+=((5-A)*10);
    return ret;
}
il bool Check_Door(int &x,int &y)
{
    bool flag=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            if(!vis[i][j][0]||!vis[i][j][1])
            {
                if((x==-1&&y==-1)||Evaluate(i,j)>Evaluate(x,y))
                    x=i,y=j,flag=1;
            }
        }
    int E=Evaluate(x,y);
    if(flag)
    {
    	if((E/1000)%10==2)
    		return 1;
    	return 0;
    }
    return flag;
}
il int Get_need(int x,int y,int h)
{
    int ret=0;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if((i==Hr&&j==Hc)||(i==Hr&&j==Hc+Hy-1)||(i==Hr+Hx-1&&j==Hc)||(i==Hr+Hx-1&&j==Hc+Hy-1)||(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2))
                continue;
            for(ri k=(i==x&&j==y)?2:0;k<h;k++)
                if(!vis[i][j][k])
                    vis[i][j][k]=1,ret++;
        }
    int E=Evaluate(x,y);
    ret+=(5-(E/10)%10);
    Corner(x,y,1);
    return ret;
}
il int Check_Corner(int h)
{
    int ret=0;
    for(ri i=0;i<h;i++)
    {
        if(!vis[Hr][Hc][i])
            ret++;
        if(!vis[Hr][Hc+Hy-1][i])
            ret++;
        if(!vis[Hr+Hx-1][Hc][i])
            ret++;
        if(!vis[Hr+Hx-1][Hc+Hy-1][i])
            ret++;
    }
    return ret;
}
il void Fix(int h)
{
    bool door=0,corner=0;
    int x=-1,y=-1;
    door=Check_Door(x,y);
    if(x!=-1&&y!=-1)
    {
    	int E=Evaluate(x,y);
    	num+=(2-(E/1000)%10);
    }
    else
    	num+=2;
    int need=Get_need(x,y,h);
    if(num<need)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL\n");
        return;
    }
    num-=need;
    printf("GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE\n");
    if(!door)
        printf("HOUSE HAS NO DOOR\n"),perfect=0;
    else
        printf("DOOR IS OK\n");
    if(need>0)
        printf("WALL NEED TO BE FIXED\n"),perfect=0;
    else
        printf("WALL IS OK\n");
    need=Check_Corner(h);
    if(need>0)
        printf("CORNER NEED TO BE FIXED\n"),perfect=0;
    else
        printf("CORNER IS OK\n");
    if(need>num)
        num=0;
    else
        num-=need;
    printf("CIRNO FINALLY HAS %d ICE_BLOCK(S)\n",num);
    if(perfect)
        printf("CIRNO IS PERFECT!\n");
}
il void Remove_Blocks(int h)
{
    memset(f,-1,sizeof(f));
    if(!BFS(Hr,Hc,h,0,1))
    {
        printf("SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS\n");
        return;
    }
    int dir=1;
    for(ri i=Hr;i<=Hr+Hx-1;i++)
        for(ri j=Hc;j<=Hc+Hy-1;j++)
        {
            if(i>=Hr+1&&i<=Hr+Hx-2&&j>=Hc+1&&j<=Hc+Hy-2)
                continue;
            for(ri k=0;k<h;k++)
                if(vis[i][j][k]&&f[i][j][k]==-1)
                    BFS(i,j,k,dir++,1);
        }
    Fix(h);
}
il void Make_Roof()
{
    int h=Get_Height();
    int need=Get_Need(h);
    if(num<need)
    {
        printf("SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF\n");
        return;
    }
    int S=(Hx-2)*(Hy-2)*h;
    if(h<2||S<2)
    {
        printf("SORRY CIRNO,HOUSE IS TOO SMALL\n");
        return;
    }
    num-=need;
    int num1=0,num2=0;
    for(ri i=Hr+1;i<=Hr+Hx-2;i++)
        for(ri j=Hc+1;j<=Hc+Hy-2;j++)
        {
            for(ri k=0;k<h;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num1++,num++,perfect=0;
            for(ri k=h+1;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;
        }
    for(ri i=0;i<n;i++)
        for(ri j=0;j<n;j++)
        {
            if(i>=Hr&&i<=Hr+Hx-1&&j>=Hc&&j<=Hc+Hy-1)
                continue;
            for(ri k=0;k<Hm;k++)
                if(vis[i][j][k])
                    vis[i][j][k]=0,num2++,num++,perfect=0;
        }
    printf("%d ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED\n",num1);
    printf("%d ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED\n",num2);
    Remove_Blocks(h);
}
int main()
{
    n=read();
    Hm=read();
    Hr=read(),Hc=read(),Hx=read(),Hy=read();
    m=read();
    for(ri i=1;i<=m;i++)
    {
        char opt[MAXN];
        memset(opt,0,sizeof(opt));
        Getstr(opt);
        if(strcmp(opt,"ICE_BARRAGE")==0)
        {
            int r=read(),c=read(),dir=read(),s=read();
            printf("CIRNO FREEZED %d BLOCK(S)\n",Spell_Card(r,c,dir,s));
        }
        else if(strcmp(opt,"MAKE_ICE_BLOCK")==0)
        {
            int k=Make();
            printf("CIRNO MADE %d ICE BLOCK(S),NOW SHE HAS %d ICE BLOCK(S)\n",k,num);
        }
        else if(strcmp(opt,"PUT_ICE_BLOCK")==0)
        {
            int r=read(),c=read(),h=read();
            Put(r,c,h);
        }
        else if(strcmp(opt,"REMOVE_ICE_BLOCK")==0)
        {
            int r=read(),c=read(),h=read();
            Remove(r,c,h);
        }
        else
            Make_Roof();
    }
    return 0;
}

0%